package com.zxy.javaarithmetic.LinearList;

/**
 * @author : Shonn.Zhang
 * @email : shonn.zhang@mart.blue
 * @time : 2021/9/2 10:10
 * @desc : 双向链表
 */
public class DoubleLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;

    private static class Node<T> {
        public T val;
        public Node<T> pre;
        public Node<T> next;

        public Node(T val) {
            this.val = val;
        }
    }

    public void add(T data) {
        addLast(data);
    }

    public void addFirst(T data) {
        if (head == null) {
            head = tail = new Node<>(data);
        } else {
            Node<T> newHead = new Node<>(data);
            newHead.next = head;
            head.pre = newHead;
            head = newHead;
        }
        size++;
    }

    public void addLast(T data) {
        if (tail == null) {
            head = tail = new Node<>(data);
        } else {
            Node<T> newTail = new Node<>(data);
            tail.next = newTail;
            newTail.pre = tail;
            tail = newTail;
        }
        size++;
    }

    public void remove(Node<T> node) {
        if (size == 0) return;
        Node<T> pre = node.pre;
        if (pre != null) {
            pre.next = node.next;
            node.pre = null;
        }
        Node<T> next = node.next;
        if (next != null) {
            next.pre = pre;
            node.next = null;
        }
        size--;
        if (size == 0) {
            head = tail = null;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public Node<T> get(int index) {
        if (index < 0 || index >= size) return null;

        Node<T> node;
        if (index < size / 2) {
            node = head;
            for (int i = 0; i <= index; i++) {
                node = node.next;
            }
        } else {
            node = tail;
            for (int i = size - 1; i >= index; i++) {
                node = node.pre;
            }
        }

        return node;

    }


}
